1. Field of the Invention
This invention relates to a method for automatic routing of the connections between components on an integrated circuit substrate or on an interconnection board. More particularly, the invention pertains to an automatic, iterative wire routing method for global and detailed wiring for chips and higher level packages that does not require the user to specify a preferred wiring direction in each wiring plane, and the product resulting from the practice of said method.
Electrical connection of individual components on large or very large scale integrated circuits and interconnection packages, is achieved using metallic paths between the end points (or pins) which are to be connected. The paths between pins generally can be represented as lying on a grid of links and nodes arranged in a Cartesian coordinate system, or x, y, z configuration. A path between two or more pins is referred to as a net. A path between ony two pins is usually referred to as a connection. In some instances, it is necessary to use multiple levels of wiring planes wherein a path or a portion of a path must connect with another portion of the path or with a pin on a different plane. This is accomplished by using a "via" which is an etched or drilled hole in the substrate allowing a conductive path to extend from one level to another. Among the components to be connected may be one or more components referred to as a "macro" which consists of large, sophisticated subcircuits. Macros may be so densely packed that there is no space for connections to pass through these areas on the substrate. This is referred to as a blockage. Other wire path complications may arise when one net crosses over another, or when it passes too close to another net in the same or different planes resulting in cross-talk problems. Notwithstanding these restrictions, it is necessary to make the required connections automatically on the integrated circuit in the most efficient manner possible resulting in the fewest number of connections remaining to be hand embedded.
2. Description of the Prior Art
The concept of iteratively assigning net connections in accordance with a penalty function described in terms of "costs", is shown in IBM Technical Disclosure Bulletin, Volume 25, No. 7B, December 1982, pages 3619 through 3628. In the method taught by this paper, individual wire paths are routed serially using an algorithm for generating wire paths according to user specified penalty costs correlated with wiring grid locations. The wire paths are generated iteratively, with progressively higher penalty costs such as those assigned to wire path crossovers and vias. A path having the minimum penalty function is sought. IBM Technical Disclosure Bulletin, Volume 26, No. 3A, August 1983, page 934, uses capacity and estimated wiring load to provide an estimate of wiring congestion on a grid, rather than to provide an explicit wiring pattern. In contrast with the techniques described in the above discussed papers, the present invention first randomly assigns a path using a preselected simple shape for each connection. Alternative path shapes for each connection are then evaluated according to a penalty function which is defined in terms of user-specified penalty costs. This permits extendability to greater multilevel complexity, more balanced wiring and the use of fewer and directionally uncommitted planes.
U.S. Pat. No. 3,653,071 issued on Mar. 28, 1972, to Hill et al entitled, "Process For Producing Circuit Artwork Utilizing a Data Processing Machine" and U.S. Pat. No. 3,653,072 also issued on Mar. 28, 1972, to Ballas et al also entitled, "Process for Producing Circuit Artwork Utilizing a Data Processing Machine" both teach a method of routing nets between terminal pins of individual elements using a numbered ordered maze. It takes into account input information such as cell pin identification (including X and Y coordinates) along with "from-to" information. Starting at a first pin located, a numbered ordered maze is constructed which identifies all node to node distances, until the net is completed. At that point, a black track routine is used to establish the shortest path within the maze back to the pin at which the maze started. The routing method makes three passes wherein a pass constitutes attempted routing of all nets or some lesser number specified by the user of the method. Rerouting of nets which have failed in one pass is attempted in subsequent passes. U.S. Pat. No. 3,603,771 issued on Sept. 7, 1971, to Isett entitled, "Input/Output Signal Point Assignment" pertains to a method of assigning wiring connections in order of descending length, i.e., it starts with the longest connection to be routed, than the next longest and so forth. This procedure is done first with respect to nodes within rows and then to nodes between rows.
U.S. Pat. No. 3,654,615 to Freitag entitled, "Element Placement System" pertains to a method of connecting circuit elements in accordance with a preselected wiring pattern, such as the well known Lee algorithm discussed hereinbelow.
A number of algorithms have been developed to find optimal routing of individual connections. C. Y. Lee, "An Algorithm for Path Connections and Its Applications", Vol. EC-10, IRE Transactions on Electronic Computers, pages 316 to 365 (September 1961), pertains to an algorithm for finding the shortest path between two points which avoids certain prescribed obstacles.
The Lee path connection algorithm is further developed by F. Rubin, "The Lee Path Connection Algorithm", IEEE Transactions on Computers, Vol. 23, No. 9, (September 1974) and (erratum) IEEE Transactions on Computers, p. 208, (February 1976). Rubin modifies the Lee algorithm by introducing codings for the pins to be connected which will allow the correct operation of the algorithm under the most general path cost function using the minimum number of states possible, i.e., six states per cell. In addition, Rubin teaches adding the distance to the goal to the path cost function to substantially reduce the time required to execute the Lee algorithm.
In another paper by F. Rubin, entitled "An Iterative Technique for Printed Wire Routing," 11th Design Automation Workshop, page 308 (1974), a Lee type algorithm mazerouter is used to find a lowest cost path according to a penalty function which contains path length, crossing and adjacency penalty costs with the purpose of reducing the number of connections remaining unrouted. Rubin states that without the adjacency penalty costs, his method "makes some fairly small improvement in the number of wires routed." The present invention differs in several respects from the teachings of Rubin. Within the context of the present invention, it has been discovered that a substantial reduction in the number of unrouted connections can be achieved using a crossing costs, but no adjacency cost, in the penalty function.
Furthermore, the present invention uses a penalty function with appropriate costs parameters to facilitate "wrong-way" or multidirectional wiring within a plane. In addition, the present invention uses an appropriate penalty function to accomplish a variety of design goals, rather than just to minimize the number of unrouted nets. These design goals include reduction of total wire length, reduction of via count, reduction of cross-talk noise, and satisfaction of minimum and maximum wire length constraints for particular connections. R. Korn, "An Efficient Variable-Cost Maze Router", Paper 27.3, 19th Design Automation Conference IEEE, pages 425 through 431 describes the result of wire path routing through using the Rubin strategy of adding the distance to goal to the path cost function given in the first of the Rubin papers above described. In addition, Korn modifies the wire route algorithm by introducing a cost function having a value which is dependent upon whether the path is proceeding toward or away from the target.
P. E. Hart et al, "A Formal Basis for the Heuristic Determination of Minimum Cost Paths", IEEE Transactions of Systems Science and Cybernetics, SS-4, No. 2, pages 100 through 107 (1968), describes how a heuristic approach can be combined with a mathematical approach in an algorithm for finding an optimal wire path between two points, i.e., one with a minimum cost.
S. Kirkpatrick, C. D. Gelatt, Jr., and M. P. Vecchi (Science 220, p. 2671, 5/13/83) describe a wiring method that is limited to `L` and `Z` wire shapes within a single layer, considers at each step of the routing procedure only one possible alternative wire path for each wire, evaluates a specific penalty function equal to the sum of the squares of the number of wires on each link of the grid, and replaces a path by its alternative depending on the value of the penalty functions and on the choice of a random number. The feature of randomness is required by their approach to avoid becoming locked into a poor wiring solution. The present invention differs in several respects, including the following: The present invention achieves near-optimal assignment of connections to levels (planes or plane pairs) of the interconnection package; a more general penalty function of greater utility is used; a large number of possible moves are considered for each connection at each pass, allowing a near-optimal solution to be reached without introducing a random element; an `uphill` option is provided that differs from the `Metropolis Monte-Carlo` method of the cited reference and provides greater facility for improving the wiring layout; and more general path types and routing methods are provided, providing the ability to do global and detailed wiring for problems of realistic and useful complexity.